The Internet is growing explosively. This explosive growth is reflected in both the number of devices using the Internet and the rate at which data packets are communicated between these devices.
When a sending device and a receiving device exchange a packet via the Internet, the packet generally passes through a number of network elements connected to the Internet between the sending device and the receiving device. A network element might include a switch, a router, or generally any network node. The packet is said to hop from one device to a next device in transit between the sending device and the receiving device via the Internet. Thus, a next device is often called a next hop.
Every device connected to the Internet is identified by a bit-sequence called an address. The number of Internet addresses is also growing explosively. In order to cope with this latter growth, the Internet Protocol (IP) supports multiple address encoding schemes, with the result that Internet address bit-sequences are not all the same length.
A sending device encodes within each packet an address corresponding to the receiving device, which is generally called a destination address. When a packet arrives at a network element, the network element examines the destination address encoded in the packet in order to select an appropriate next hop to forward the packet toward the receiving device. Generally, this next hop selection is made from among a relatively small number of devices that are proximate to the network element in the network.
Typically, the network element selects a next hop device using a routing table that correlates destination addresses to addresses or ports associated with the proximate devices. Usually, the routing table does not include a separate record for each destination address, but instead includes one record for each family of destination addresses, for example destination addresses sharing a common bit-sequence prefix. Thus in order to identify a correlated next hop device, the network element searches the routing table for the longest prefix that matches the destination address encoded in a packet being routed. However, efficiently searching the routing table for a longest matching prefix rather than a complete address can be complicated because there may exist several matching prefixes whereas only the longest matching prefix is being sought. Thus the search algorithm must locate a matching prefix and then determine that no longer matching prefix exists.
It will be appreciated that the explosive growth in both the number of potential destination addresses and the rate at which packets must be routed is placing significant demands on network elements. In fact, it is predicted that a new generation of network element will have to route millions of packets per second. Thus, the routing table lookup mechanism is critical to efficiently operating a network element and the Internet as a whole. Unfortunately, conventional routing table lookup mechanisms are insufficient for this task because they are too slow.
What is needed therefore is a way to encode pre-defined codes such as address-prefix bit-sequences and a way to locate a longest matching pre-defined code to a given code.